//https://www.nowcoder.com/practice/cf7e25aa97c04cc1a68c8f040e71fb84?tpId=13&tqId=23455&ru=%2Fpractice%2F445c44d982d04483b04a54f298796288&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
//https://leetcode.cn/problems/xu-lie-hua-er-cha-shu-lcof/submissions/
//思路1：1.考察前序遍历 2.char** 指针操作；3.std::string 转换为 char*
//其他:1.重点题目！！！；2.研读代码；2.leetcode 解法比较好；
// comments:good

#include <algorithm>
#include <climits>
#include <queue>
#include <vector>
#include <string>
#include <string.h>
#include <list>

using namespace std;

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
  public:
    //处理序列化的功能函数（递归）
    void SerializeFunction(TreeNode* root, string& str) {
        //如果指针为空，表示左子节点或右子节点为空，用#表示
        if (root == nullptr) {
            str += '#';
            return;
        }
        //根节点
        string temp = to_string(root->val);
        str += temp + '!';// 加!，区分节点
        //左子树
        SerializeFunction(root->left, str);
        //右子树
        SerializeFunction(root->right, str);
    }
    char* Serialize(TreeNode* root) {
        //处理空树
        if (root == nullptr)
            return "#";
        string res;
        SerializeFunction(root, res);
        //把str转换成char
        char* charRes = new char[res.length() + 1];
        strcpy(charRes, res.c_str());
        charRes[res.length()] = '\0';
        return charRes;
    }
    //处理反序列化的功能函数（递归）
    TreeNode* DeserializeFunction(char** str) {
        //到达叶节点时，构建完毕，返回继续构建父节点
        //双**表示取值
        if (**str == '#') {
            (*str)++;
            return nullptr;
        }
        //数字转换
        int val = 0;
        while (**str != '!') {
            val = val * 10 + ((**str) - '0');
            (*str)++;
        }
        TreeNode* root = new TreeNode(val);
        (*str)++;
        //反序列化与序列化一致，都是前序
        root->left = DeserializeFunction(str);
        root->right = DeserializeFunction(str);
        return root;
    }
    TreeNode* Deserialize(char* str) {
        //空序列对应空树
        if (*str == '#') {
            return NULL;
        }
        TreeNode* res = DeserializeFunction(&str);
        return res;
    }
};



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution2 {
public:
    // 先序遍历
    void preOrder(TreeNode* root, string& str) {
        if (root == nullptr) {
            str += "null,";
        } else {
            str += to_string(root->val) + ",";
            preOrder(root->left, str);
            preOrder(root->right, str);
        }
    }

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res;
        if(root == nullptr) {
            return "";
        }
        preOrder(root, res);
        return res;
    }

    // 注意DFS的元素列表对应的二叉树不唯一
    TreeNode* preOrder(list<string>& dataArray) {
        if (dataArray.front() == "null") {
            dataArray.erase(dataArray.begin());
            return nullptr;
        }
        TreeNode* root = new TreeNode(stoi(dataArray.front()));
        dataArray.erase(dataArray.begin());
        root->left = preOrder(dataArray);
        root->right = preOrder(dataArray);
        return root;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data == "") {
            return nullptr;
        }
        // 根据','把string分割开得到先序遍历元素的数组
        list<string> dataArray;
        string str;
        for (auto& ch : data) {
            if (ch == ',') {
                dataArray.push_back(str);
                str.clear();
            } else {
                str.push_back(ch);
            }
        }
        if(!str.empty()) {
            dataArray.push_back(str);
            str.clear();
        }
        // 先序遍历构建二叉树
        return preOrder(dataArray);
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));